"""
交换单链表里两个链点
给定两个值，如果这两个值都在单链表的链点中，即交换这两个链点在单链表的位置。
举例：
    1->2->3->4->5
    input:1 4 output:4->2->3->1->5
目标：
    交换两个链点在链表中的位置
    不改变其他链点在链表中的位置
思路：
    采用 insert 的思想，对于要交换的两个链点 d1 d2，各自声明新的 D1 D2 ，
    使 D1=d1, D2=d2,然后把 然后再根据 d1 d2 的位置，改变索引的位置，即完成交换的全部操作
"""


class Node:
    def __init__(self, data):
        self.data = data     # 数据域
        self.next = None     # 指针域


class LinkedList:
    def __init__(self):
        self.head = None

    # 遍历链表，打印元素
    def print_list(self):
        print("linked_list: ")
        temp = self.head
        new_list = []
        while temp is not None:
            new_list.append(temp.data)
            temp = temp.next
        print(new_list)

    def insert(self, new_data):
        new_node = Node(new_data)
        new_node.next = self.head
        self.head = new_node

    def swap_nodes(self, d1, d2):
        prevD1 = None
        prevD2 = None
        if d1 == d2:
            return
        else:
            D1 = self.head
            while D1 is not None and D1.data != d1:
                prevD1 = D1
                D1 = D1.next
            D2 = self.head
            while D2 is not None and D2.data != d2:
                prevD2 = D2
                D2 = D2.next

            if D1 is None and D2 is None:
                return

            if prevD1 is not None:
                prevD1.next = D2
            else:
                self.head = D2
            if prevD2 is not None:
                prevD2.next = D1
            else:
                self.head = D1
            temp = D1.next
            D1.next = D2.next
            D2.next = temp


if __name__ == '__main__':
    lst = LinkedList()
    lst.insert(5)
    lst.insert(4)
    lst.insert(3)
    lst.insert(2)
    lst.insert(1)
    lst.print_list()
    lst.swap_nodes(1, 4)
    print("After swapping: ")
    lst.print_list()









